package try01;

import java.util.*;

public class NQueensII {
	public void tester() {
		totalNQueens(9);
	}
	public int totalNQueens(int n) {
        boolean [][] board = new boolean [n][n];
        
        if(n > 0) q(board, n, n);
        System.out.println("size: "+size);
        System.out.println("count: "+count);
        return size;
    }
        
    public int size = 0;
    public int count = 0;
    
    public void q(boolean [][] board,int curr, int n) {
    	count++;
    	if(curr == 0) {
    		size++;
    		return;
    	}
    	else {
    		for(int j = 0 ; j < board.length ; j++) {
				if(board[n-curr][j] == false) {
					board[n-curr][j] = true;
					boolean [][] board2 = deepcopy(board);
					
					mark(board2, n-curr, j);
					
					q(board2, curr-1, n);
				}
			}
    	}
    }
    
    public boolean [][] deepcopy(boolean [][] s) {
    	boolean [][] d = new boolean [s.length][s.length];
    	for(int i = 0 ; i < s.length ; i++) {
    		for(int j = 0 ; j < s.length ; j++) {
    			d[i][j] = s[i][j];
    		}
    	}
    	return d;
    }
    
    public void mark(boolean [][] board, int r, int c) {
    	int n = board.length;
    	for(int i =0 ; i < n ; i++) {
    		board[r][i] = true;
    		board[i][c] = true;
    		
    		if(r + i < n && c + i < n)
    			board[r+i][c+i] = true;
    		if(r + i < n && c - i >= 0)
    			board[r+i][c-i] = true;
    		if(r - i >= 0 && c + i < n)
    			board[r-i][c+i] = true;
    		if(r - i >= 0 && c - i >= 0)
    			board[r-i][c+-i] = true;
    	}
    }
}